package sword.chapter2Array;

/**
 * 乘积小于k的子数组
 * 同向双指针
 *
 * @author K
 * @date 2021-11-01 22:23
 */
public class S9NumSubarrayProductLessThanK {
    public static void main(String[] args) {
        int[] nums = new int[]{10, 5, 2, 6,};
        int i = numSubarrayProductLessThanK(nums, 100);
        System.out.println();
    }

    public static int numSubarrayProductLessThanK(int[] nums, int k) {
        int product = 1;
        int left = 0;
        int count = 0;
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
            while (left <= right && product >= k) {
                product /= nums[left++];
            }
            // 取反，例如4个数，就有4数小于k，打草稿找规律
            count += right >= left ? right - left + 1 : 0;
        }
        return count;
    }
}
